package array.minSubArrayLen;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2021/12/15 11:08
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 */
public class Title76 {
    public static void main(String[] args) {
        String result = minWindow("cabwefgewcwaefgcf", "cae");
        System.out.println(result);
    }

    private static Map<Character, Integer> hashT = new HashMap<>();
    private static Map<Character, Integer> hashS = new HashMap<>();

    private static String minWindow(String s, String t) {
        if (t.length() > s.length()) {
            return "";
        } else if (t.length() == 1 && s.contains(t)) {
            return t;
        }
        for (int i = 0; i < t.length(); i++) {
            hashT.put(t.charAt(i), hashT.getOrDefault(t.charAt(i), 0) + 1);
        }
        String result = "";
        //记录s中出现t的字母索引
        List<Integer> index = new ArrayList<>();
        int indexS=0;
        int minLen = Integer.MAX_VALUE;
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            //在s找到第一个包含t中字母的索引
            if(hashS.size()==0){
                for (int i = 0; i < s.length(); i++) {
                    if (t.contains(s.charAt(i) + "")) {
                        //记录第一个字母
                        hashS.put(s.charAt(i), 1);
                        index.add(i);
                        right = i;
                        left = i;
                        break;
                    }
                }
                if (hashS.size() == 0) {
                    return "";
                }
            }else{
                if (t.contains(s.charAt(right) + "")) {
                    index.add(right);
                }
                hashS.put(s.charAt(right), hashS.getOrDefault(s.charAt(right),0) + 1);
                //查询subS是否包含T
                while (check()) {
                    if (right - left + 1 < minLen) {
                        result = s.substring(left, right + 1);
                        minLen = right - left + 1;
                    }
                    hashS.put(s.charAt(index.get(indexS)), hashS.get(s.charAt(index.get(indexS))) - 1);
                    left = index.get(++indexS);
                }
            }
        }
        return result;
    }


    private static boolean check() {
        //判断子串是否包含t
        Set<Character> keySetT = hashT.keySet();
        for (char c : keySetT) {
            if (!(hashS.containsKey(c) && hashS.get(c)>=hashT.get(c))) {
                return false;
            }
        }
        return true;
    }
}
